# Interval DP

• 2026년 7월 30일 알고리즘
  동적 계획법 ③ — 구간을 어디서 자를 것인가

  행렬 M₁×…×Mₙ을 곱할 때 결과는 같아도 곱셈 횟수는 괄호를 어디에 치느냐로 달라진다. (3×2)(2×4)(4×2)는 48번 대 28번. '이 구간의 마지막 곱을 어디서 하는가'라는 결정에서 M[i,j]=minₖ(M[i,k]+M[k+1,j]+d_{i-1}d_k d_j)를 세우고, 짧은 구간부터 채워 O(n³)에 푼다. dp-2의 결정 사고를 원소에서 구간으로 확장한다.